CC Chapter 5
Multiversion Concurrency Control
こちらの論文を読んだときのほうが理解が深い
5.1 Introduction
In a multiversion concurrency control algorithm, each Write on a data item $ x produces a new copy (or version) of $ x.
これがSingle-Version(1Vと言う)のデータベースとの違い．
データはそれまでのversionの履歴をリストとして持つ． For each Read($ x), the scheduler not only decides when to send the Read to the DM, but it also tells the DM which one of the versions of $ xto read.
何を読むべきかという添字がつくのがMulti-versionのread命令の特徴．
e.g. $ r(x_1) : version(1)のxを読む．
Multiversion化の恩恵はReadにある．
Read命令の受付がどれだけ遅かろうと，古いVersionが残っているのならそれを返せばよいから．
1VはすなわちIn-Placeである．だから，値が書き換わってしまったら，Abortするケースが多い． Consはリストの管理．
無限に肥大化していくリストというのはよろしくない．
どこかでGCする必要がある．
リカバリにも問題は付きまとう．
Versionの概念はデータベースの内部でだけ扱う．
ユーザにはこのような概念は透過的に扱えるようにする．
これについてはこの章で議論しない
Analyzing Correctness
まず，Serializability correctnessを拡張する．
これまでこの書で議論されてきたSerializabilityを1V-SRとおく．
すなわち，SingleVersionで直列実行した際のHistoryと等価であるということ．
しかしMultiversion Databaseは当然，生成するHistoryはMultiversionである．
だから，Multiversion Historyが1V-SRのHistoryと等価かどうかを証明するのがMVのCorrectness.
突き詰めると，トランザクションのIsolation/Serializableとは，どんな物理環境でも直列実行と等価な処理結果が得られる，というセマンティクスであり，そういう契約なので，これを証明する必要があるのは道理 たとえば以下を考える
$ H_1 = w_0(x_0) c_0 w_1(x_1) c_1 r_2(x_0)w_2(y_2)c_2
$ H_2 = w_0(x) c_0 w_1(x) c_1 r_2(x)w_2(y)c_2
違いはVersionをdropしただけ．
重要な示唆として，$ H_1と$ H_2は命令列の並びが同じである
ということはこれまでの1V-Correctnessのやり方だと，命令列が同じだから，この二つのHistoryはEquivalent.
だがしかし$ r_2(x_0)は明らかにややこしい議論を呼んでいる．直感的にもこの二つはequivalentではない．
CSRのグラフを見てみても，$ H2では$ T1 \to_{wr} T2だが $ H1ではこれは無い．
つまり，これまでのCorrectnessのやり方を変える必要がある．
さて，serial 1V historyとserial MV hisotryがequivalentであることを証明したい．
たとえばSerialization Graph(SG)を描いてacyclicなら...という論法を使いたい
だが，SGが一致していてもreads-fromが一致しないので，この論法は意味がない
一例
$ H_3 = w_0(x_0) w_0(y_0) c_0 \ r_1(x_0) r_1(y_0) w_1(x_1) w_1(y_1) c_1 \ r_2(x_0) r_2(y_1) c_2
$ SG(H_3) = T_0 \to T_1 \to T_2$ T_0 \to T_2
これはSerial and Acyclicだが，Serial 1V Historyとは一致しない．
たとえば$ T_0 \to T_1 \to T_2の Serial 1V historyとはReads-Fromが一致しない
この場合$ T_2の$ r_2(x)は$ T_1のものを読んでいるので$ H_3とは違う．
くわえて$ T_0 \to T_2 \to T_1とも一致しない．
この場合も同じで，今度は$ yのversionが合わない．
以上から，Serial MV Scheduleの中で，さらに，Serial 1V HistoryとReads-Fromが一致する場合のみSerializableである
これを1-SR MV Historyと呼ぶ．
この1-SR MV Historyを作るためには，やはりGraphの考え方に持って行きたい．
そのためには，先ほど見たように，これまでのGraphのやりかたではダメなので，新しいセマンティクスを作る．
この新しいGraphをMultiversion View Serialization Graph(MVSG)と呼ぶ．
An MV history is equivalent to a 1-serial MV history iff it has an acyclic MVSG.
これが要件である．
以下にMVSGの使い方を要約する
まずMV HistoryからMVSGを描く．
MVSGがacyclicなら，トポロジカルソート可能
トポロジカルソートした際，nodeはトランザクションなので，$ T_0 \to T_1 \to T_2のような全順序が得られる
この全順序でトランザクションを直列実行するとSerial 1V Historyが得られる
このSerial 1V Historyと，もとのMV HistoryのReads-Fromが一致するなら，もとのHisotryは1-SR MV History!
はい，では証明．
5.2 MULTIVERSION SERIALIZABILITY THEORY
$ T = {T_0, ...T_n}とおく．
$ T_iはすなわち$ <_iであり$ 0 \leq i \leq n
$ T_iの命令列，たとえば$ r_i(x)や$ w_i(y)をMultiversion Scheduleに拡張する．
このTranslation functionを$ hとする．これにより$ h(r_i(x)) = r_i(x_j)のような結果が得られる．
一応言うと$ jは$ j \in {0,...n}つまりいずれかの$ i
complete multiversion historyを$ Hと定義する．
complete MV historyは以下を満たすものと定義する．
Definition of Complete MV History
1. $ H = h(\cup^n_{i=0}) for some translation function $ h
2. for each $ T_i and all operations $ p_i, $ q_i in $ T_i, if $ p_i <_i q_i, then $ h(p_i) < h(q_i)
3. if $ h(r_j[x]) = r_j[x_i] , then $ w_i[x_i] < r_j[x_i]
4. if $ w_i[x] <_i r_i[x] , then $ h(r_i[x]) = r_i[x_i]
5. if $ h(r_j[x]) = r_j[x_i] , $ i \ne j, and $ c_j \in H, then $ c_i < c_j
一つずつ解説する．
1は，schedulerすなわちトランザクション処理のアルゴリズムが各Txの命令(r,w)をMultiversion化できる，ということ．
2は，$ hがトランザクション内の命令列の順序は変更しないということを言っている．
3は，writeされる前にその命令がreadされることはないと言っている．
5は，readがcommitされているなら，そのwriter transactionも必ずcommitされている，ということ．
この全てを満たすComplete MV Historyはpreserves reflexive reads-from relationshipsである．
(なにそれ？)
MV History Equivalence
1V HistoryがView Equivalentかどうかを調べる方法は以下だった
1. 同じ命令列からなり，同じReads-From RelationShipである
2. 同じfinal writesを持つ
これは$ T_\inftyが全データを$ \{r_\infty(x)| x \in all\ data\}しても同じ結果が帰るということ
Multiversionでは2を省いて良い．
同じ命令列からなるなら，同じWritesを持つので，問題としてどのバージョンを読むか($ h)のみ考えればよい．
Since no versions are overwritten, all Writes are effectively final writes.
Thus, if two MV histories over the same transactions have the same operations and the same reads-from relationships, then they have the same final writes and are therefore view equivalent.
つまり，Equivalence of MV historiesについては以下の命題に従う．
Proposition 5.1: Two MV histories over a set of transactions are equivalent iff the histories have the same operations.
多分，same operationsというのはversion numberが同じ場合を暗に言っている
確かにそれならEquivalentっぽい
次に，Multiversion History($ H_{MV})と1V-History($ H_{1V})のequivalenceを定義する．
まず，この二つが全単射でなければならない
言い換えると，$ H_{1V}の各ops，たとえば$ r_i(x)が$ H_{MV}において$ r_i(x_j)に出来るということ
このtranslationができないopsがあるということは全単射ではない
同じ命令列からなる，と簡単に言い換えられる
Serialization Graph
Two operations in an MV history Conflict if they operate on the same version and one is a Write.
Only one pattern of conflict is possible in an MV history: if $ p_i < q_j and these operations conflict, then $ p_i is $ w_i[x_i] and $ q_j is $ r_j[x_i] for some data item $ x
すなわち，$ w-r以外はconflictではない．
それはなぜか？
Conflicts of the form $ w_i[x_i] < w_j[x_i] are impossible, because each Write produces a unique new version.
conflictとは何かというと依存関係であり，それぞれparallelにunique versionを書くのだから$ w-w依存は無い．
Conflicts of the form $ r_j[x_i] < w_i[x_i] are impossible, because $ T_j cannot read $ x_i until it has been produced.
読んだ通り，$ r-w依存にあたるものは表現できない．
よってMV historyにおいてはreads-fromすなわち$ w-rの依存関係のみがconflictsになる．
$ w-rのみを用いて$ SG(H)を作れるということだ．ここから以下の命題が導かれる．
Proposition 5.2: Let H and H' be MV histories, If $ H \equiv H', then $ SG(H) = SG(H')
(View Equivalentつまり$ \equivなら，Reads-Fromが同じわけだから，それを使って描いたグラフも同じという理屈)
One Copy Serializability
ここでは3つのclassが出てくる．
serial
A complete MV history is serial if for every two transactions $ T_i and $ T_j that appear in $ H, either all of $ T_i's operations precede all of $ T_j's or vice versa.
Complete MV Historyにおいて，というのが重要．
Not all serial MV histories behave like ordinary serial 1V histories, for example,
$ H_3 = w_0[x_0]w_0[y_0] c_0 r_1[x_0]r_1[y_0]w_1[x_1]w_1[y_1]c_1r_2[x_0]r_2[y_1]c_2
だが，1Vとは違って↑のようなスケジュールが許される．
この場合$ T_0 \to T_1 $ T_0 \to T_2 $ T_1 \to T_2で半順序が作れる．
one-copy serial (1-serial)
A serial MV history H is one-copy serial(or 1-serial) if for all $ i,j,and$ x, if $ T_i reads $ x from $ T_j, then $ i = j, or $ T_j is the last transaction preceding $ T_ithat writes into any version of $ x.
つまりthe most recent writesを読むという縛りを$ hに入れるということ．
Since $ H is serial, the word last in this definition is well defined.
History $ H_3 is not 1-serial because $ T_2 reads $ x from $ T_0
but $ w_0[x_0] < w_1[x_1] < r_2[x_0] .
半順序が作れても$ H_3はreads the most recent writesではないので1-serialな全順序は作れない．
one-copy serializable(1-serializable)
An MV history is one-copy serializable(or 1SR) if its committed projection is equivalent to a 1-serial MV history.
まあそうかなと．
A serial history can be 1SR even though it is not 1-serial. For example,
$ H_9 = w_0[x_0]c_0 r_1[x_0] w_1[x_1] c_1 r_2[x_0]c_2
is not 1-serial sinse $ T_2 reads $ x from $ T_0 instead $ T_1. But it is 1SR, because it is equivalent to
$ H_{10} = w_0[x_0] c_0 r_2[x_0] c_2 r_1[x_0] w_1[x_1] c_1 .
なるほど．1-serialは1Vで直列実行した際と等価であるかを検証している．
対して1-serializableは，1Vで直列実行した際とView Equivalentかどうかを検証している．
To justify the value of one-copy serializability as a correctness criterion, we need to show that the committed projection of every 1SR history is equivalent to a serial 1V history.
$ C(H)が1SRなら1SRであるということを言っているようにしか見えない．
定理と証明
Theorem 5.3: Let $ H be an MV history over $ T. $ C(H)is equivalent to a serial, 1V history over $ T iff $ H is 1SR.
あるHistoryが1-SRのとき，またその時に限り，$ C(H)が1V Serial historyとView Equivalentである．
逆を言うと1V serial historyとView Equivalentでなければ1SRではないということ．
この言い方が後でグラフに使われる
Proof: (略)
日本語で読みながらメモ:
まず(if)
まず$ Hが1SRなので，$ C(H)はequivalent to 1-serial MV history.
このことから$ H'を作ってversionをdropすればserial 1V historyになる
というわけで$ H \equiv H'を示せればifは終わる
さて，$ Hが1-serialなので，ある$ w_i[x_i]と$ r_j[x_i]の間に$ w_k[x_k]は絶対ない．
あったらreads the most recent writesのdefinitionに反する
ということは，versionをdropしたことによってw-rの依存関係は変わらない
だからreads-fromも同じ！
次に(only if)
まず$ H'を$ C(H)とequivalentなserial 1V historyと仮定する
で，$ H'_sをserial MV history$ Hに変換する．
やり方としては，writeは普通に$ w_i(x) = w_i(x_i)で，readは$ r_i(x_j)
次に$ Hがcomplete MV Historyであることを示さなければならない．
先に見たcondtionの以下は既に満たしている
1. $ H = h(\cup^n_{i=0}) for some translation function $ h
2. for each $ T_i and all operations $ p_i, $ q_i in $ T_i, if $ p_i <_i q_i, then $ h(p_i) < h(q_i)
(3)は$ r_j[x]が$ w_i[x]に先行していることを全ての$ r_jについてやればよい
r-wが交差しなければいいってこと．
(4)は$ H'ではversionがdropされているうえserialなので必ずそうなる
(5)は$ H'がserialなのでcommit orderとoperation orderは一致するので大丈夫．
というわけで，$ Hはcomplete multiversion historyである．
complete multiversion historyのMV translationはreads-fromを変化させない(preserve reads-from relationshipなことは示したよね！
なので，$ H \equiv H'
すなわち$ C(H) \equiv H
あとは$ Hが1-serialであることを示せばよい．
$ H'を考えてみると1V Historyなのでwriteがintersectsしていないことがわかる
それとequivalentなのでやはり$ Hも1-serial.
ここまで難解だったが，要約するとC(H)がserial 1V HistoryとView Equivalentなら，Hは1SRということ，
言い換えると，MVSRを検証するにはSerial 1V Historyとのequivalenceを調べればいい(そしてそれしかない)ということを言っている．
The 1-Serializability Theorem
個人的な本丸．
あるMVCCアルゴリズムがcorrectかどうかを判断するには，そのアルゴリズムの出力(つまりHistory)が1SRであることを調べればよい．
これを行うために，先ほど説明したSG(Serialization Graph)を改変したものを用いる．
この改変は，全てのMVCCアルゴリズムが，各データ(タプル)の各バージョン(つまり全Write)の全順序を生成できることから着想を得たものだ．
言い換えると，MVCCでは(今の所)$ x_iの添字$ iに全順序が必ずつけられるということ．
VersionOrder
Given an MV history $ H and a data item $ x, a $ version \ order,$ \ll, for $ x in $ H is a total order of versions of $ x in $ H.
A $ version \ order for $ H is the union of the version orders for all data items.
たとえば1V-scheduleの$ w_1(x)w_2(x)w_3(x)があるとするとVersion Orderは
$ x_1 \ll x_1, x_1 \ll x_2という感じ．書込みの全順序を表す．
これを用いて$ SG(H)を$ MVSG(H,\ll)に拡張する．
MVSGでは，SGの$ w-redgeに加えて，Version Orderを用いたedgeを追加する．
for each $ r_k(x_j)and $ w_i(x_i) in $ C(H) where $ i,j, and $ kare distinct,
if $ x_i \ll x_jthen include $ T_i \to T_j, otherwise include $ T_k \to T_i.
(Note that there is no version order edge if $ j=k, that is , if a transaction reads from itself.